package com.xxd.algo.newcode.mid01.class02;

public class Code04_MaxSumInTree {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int val) {
			value = val;
		}
	}

	public static class Info {
		public int value;

		public Info(int value) {
			this.value = value;
		}
	}


	public static int maxPathSum(Node x) {
		Info info = process(x);
		return info.value;
	}

	public static Info process(Node x) {
		if (x == null) {
			return null;
		}

		Info leftInfo = process(x.left);
		Info rightInfo = process(x.right);
		int p1 = 0;
		int p2 = 0;
		int p3 = x.value;
		if (leftInfo != null) {
			p1 = p3 + leftInfo.value;
		}

		if (rightInfo != null) {
			p2 = p3 + rightInfo.value;
		}

		if (leftInfo == null && rightInfo == null) {
			return new Info(p3);
		}

		if (leftInfo != null && rightInfo != null) {
			return new Info(Math.max(p1, p2));
		}

		return new Info(leftInfo != null ? p1 : p2);
	}

	public static void main(String[] args) {
		Node head = new Node(4);
		head.left = new Node(1);
		head.left.right = new Node(5);
		head.right = new Node(-7);
		head.right.left = new Node(3);
		System.out.println(maxPathSum(head));
	}

}
